|
Job shop scheduling (or job-shop problem) is an optimization problem in computer science and operations research in which ideal jobs are assigned to resources at particular times. The most basic version is as follows: We are given ''n'' jobs ''J''1, ''J''2, ..., ''Jn'' of varying sizes, which need to be scheduled on ''m'' identical machines, while trying to minimize the makespan. The makespan is the total length of the schedule (that is, when all the jobs have finished processing). Nowadays, the problem is presented as an online problem (dynamic scheduling), that is, each job is presented, and the online algorithm needs to make a decision about that job before the next job is presented. This problem is one of the best known online problems, and was the first problem for which competitive analysis was presented, by Graham in 1966. Best problem instances for basic model with makespan objective are due to Taillard. == Problem variations == Many variations of the problem exist, including the following: * Machines can be related, independent, equal * Machines can require a certain gap between jobs or no idle-time * Machines can have sequence-dependent setups * Objective function can be to minimize the makespan, the ''Lp'' norm, tardiness, maximum lateness etc. It can also be multi-objective optimization problem * Jobs may have constraints, for example a job ''i'' needs to finish before job ''j'' can be started (see workflow). Also, the objective function can be multi-criteria. * Jobs and machines have mutual constraints, for example, certain jobs can be scheduled on some machines only * Set of jobs can relate to different set of machines * Deterministic (fixed) processing times or probabilistic processing times * There may also be some other side constraints 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Job shop scheduling」の詳細全文を読む スポンサード リンク
|